Reed-Solomon codes are nonbinary codes that can correct multiple, clustered errors, such as occur in disk data storage systems. In order to use such a code to correct errors in binary data, the data is assembled in groups of m bits. These groups represent symbols from the Galois field GF(2.sup.m). A Reed-Solomon code that corrects t errors will correct any errors in t groups of length m.
In a Reed-Solomon code, every codeword is represented by a code polynomial EQU C(x)=c.sub.n-1 x.sup.n-1 +c.sub.n-2 x.sup.n+2 + . . . +c.sub.0,
where
c.sub.0, c.sub.1, . . . , and c.sub.n-k-1 PA0 c.sub.n-k, c.sub.n-k+1, . . . , and c.sub.n-1 PA0 c.sub.0, c.sub.1, c.sub.2, . . . , and c.sub.n-k-1 PA0 c.sub.n-1, c.sub.n-2, . . . , and c.sub.n-k
are check symbols and
are data symbols. The code is characterized by the generator polynomial g(x). The degree of a polynomial g(x) is equal to the code redundancy n-k. The period T of a polynomial g(x) (the minimum T, such that g(x) divides x.sup.T -1) is equal to the code length. Every code polynomial can be expressed as a multiple of g(x).
The check symbols
are generated from data symbols
by dividing the "data" polynomial EQU x.sup.n-k (c.sub.n-1 x.sup.k-1 +c.sub.n-2 x.sup.k-2 + . . . +c.sub.n-k+1 x+c.sub.n-k)
by g(x). The "check" polynomial EQU c.sub.n-k-1 x.sup.n-k-1 +c.sub.n-k-2 x.sup.n-k-2 + . . . +c.sub.1 x+c.sub.0
is the "remainder" of this division.
In decoding, the received codeword r(x) is divided by g(x). If the remainder is equal to 0, it it assumed that there are no errors. Otherwise, it is concluded that an error has occurred and an error correction routine is invoked.
The choice of a generator polynomial g(x) determines the error correction capability and the complexity of the encoding and decoding circuitry.
By reducing the number of different nonzero coefficients of the generator polynomial g(x), the number of electrical circuit components for encoding and decoding (error detection) can be reduced.
The error correction routine calculates syndromes S.sub.i from S(x), the remainder of the division of the received codeword r(x) by the generator polynomial g(x) EQU S.sub.i =S(.alpha..sup.i),
where EQU S(x)=r(x) mod g(x) and .alpha..sup.i
are roots of the polynomial g(x), .alpha. is a primitive element of the Galois field GF(2.sup.m).
Error locations and values are calculated from error location and error evaluator polynomials, which are computed from the syndromes. The general algorithm to find an error location polynomial is the Berklekamp-Massey algorithm described in Chapter 9 of Error Correcting Codes by Peterson and Weldon, MIT Press, second edition (1972). Once the error location polynomial is computed, the error location is calculated using Chien's search algorithm. Both procedures (Massey-Berklekamp's and Chien's) require a significant number of calculations.
These procedures are a part of the multiple error correction system described in the U.S. Pat. No. 4,413,339, which issued to C. Riggle et al. The C. Riggle et al system implements a Reed-Solomon code with 10-bit symbols. The redundancy of the code is 17 symbols, i.e. 170 bits. The length of the code is equal to (2.sup.10 -1) symbols. The code can correct errors in up to eight symbols. The decoder of the C. Riggle et al system calculates S(x) using the same circuitry used by the encoder. The check portion d(x) of the received codeword r(x) is stored in a buffer. The data portion of r(x) is encoded using an encoder which produces a checksum d.sub.1 (x). The symbols of d.sub.1 (x) and d(x) are XOR'ed to produce S(x). Note, that the C. Riggle et al system needs a substantial amount of memory to store 170 check bits. With 170 check bits, the C. Riggle et al system corrects single burst errors up to 71 bits and double bursts errors up to 31 bits. Additionally, the C. Riggle et al system needs eight combinatorial circuits for multiplication by Galois field elements and 13 half adders.
The C. Riggle et al system provides a means for rapidly correcting a single symbol error using log and antilog tables which represent elements of Galois field GF(2.sup.10). However, the two tables need 2*(2.sup.10 -1)*10 bits, i.e. 2558 bytes of ROM.
The C. Riggle et al system is not flexible. Using it, one can encode every block of data up to (10*(2.sup.10 -1)-170) bits in length. Independent of block length, the system needs 170 bits of check bits. In many practical situations it is desirable to have a system which can change redundancy dependent on different block size, i.e. use less redundancy for a smaller block size. Moreover, it is desirable that this reconfiguration, from one block size to another, be implemented with a minimum number of electrical components.
The U.S. Pat. No. 4,142,174, which issued to C. Chen et al describes a high speed decoding scheme for Reed-Solomon code with 8-bit symbols. The C. Chen et al code corrects errors in three symbols. The C. Chen et al scheme does not use an iterative Berlekamp-Massey algorithm to compute error location polynomial. Instead, it provides a method based on the solution of a system of linear equations to find the coefficients of an error location polynomial. Note that in the case of three symbol errors, solving the system of linear equations requires a significant number of computations.
The generator polynomial g(x) of the C. Chen et al system has a form EQU g(x)=(x+1)(x+.alpha.)(x+.alpha..sup.2)(x+.alpha..sup.3)(x+.alpha..sup.4)(x+ .alpha..sup.5),
where .alpha. is a primitive element of GF(2.sup.8). This polynomial has six coefficients not equal to zero or one. Therefore, the encoder of this polynomial requires six combinatorial circuits to implement multiplication of Galois field elements.
In the U.S. Pat. No. 4,360,916, which issued to S. Kustedjo et al. and the U.S. Pat. No. 4,498,175, which issued to M. Nagumo et al., a loop search procedure is disclosed to find both roots x.sub.1 and x.sub.2 of an equation EQU .sigma.(X)=0,
where .sigma.(x) is an error location polynomial. Since the loop search procedure is used twice, once for each root, the procedure is quite time consuming.
In disk data storage systems, data is commonly protected by an error correcting code, while the associated header is commonly protected by an error detecting code. A typical error detecting code is the CRC-CCITT code (widely used in data communication) which has a generator polynomial x.sup.16 +x.sup.12 +x.sup.5 +1. The CRC-CCITT code detects all single bursts errors of sixteen bits or less and double bursts errors of four bits or less. It is bit serial.
For systems with high data transfer rate, bit serial data transfer might be a drawback.
For additional background information, the reader is referred to Error Correcting Codes by Peterson and Weldon, MIT Press, Cambridge, Mass., second edition (1972); Error Control Coding; Fundamental And Application by G. Lin and D. J. Costello, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1983 edition; "Interface Between Data Terminal Equipment (DTE) And Data Circuit-Terminating Equipment (DCE) For Terminal Operations In Packet Mode On Public Networks", CCITT Recommendation X.25, With Plenary Assembly, Doc. 7, Geneva, Switzerland, 1980; and "Parallel CRC Lets Many Lines Use One Circuit", by A. K. Pandeya, Computer Design, September 1975, vol. 14, No. 9, p. 87-91.